Depth-First Search (DFS)

Depth-First Search (DFS) is a fundamental algorithm used in graph theory to traverse or search through the nodes of a graph in a systematic manner. DFS explores as deep as possible along each branch before backtracking, making it an efficient algorithm for tasks that need to explore all the nodes in a graph thoroughly.

Algorithm Workflow

DFS can be implemented using both recursive and iterative approaches, typically using a stack data structure. The basic steps involved in the DFS algorithm are as follows:

1. Initialization: Start at the selected node, marking it as visited.
2. Stack Operations: Push the starting node onto a stack.
3. Traversal:
   • Pop a node from the stack to process it.
   • Check all adjacent nodes of this node.
   • If an adjacent node has not been visited, mark it as visited and push it onto the stack.
   • Repeat until the stack is empty.

Complexity

Time Complexity

The time complexity of DFS is $O(V + E)$, where $V$ is the number of vertices and $E$ is the number of edges in the graph.

Space Complexity

The space complexity can go up to $O(V)$ in the worst case to store the stack required for the traversal.

Recursive Implementation

def dfs_recursive(graph, vertex, visited=None):
    if visited is None:
        visited = set()
    visited.add(vertex)
    print(vertex, end=' ')  # Process the vertex as needed

    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

# Example usage
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
dfs_recursive(graph, 'A')

Iterative Implementation

from collections import deque

def dfs_iterative(graph, start):
    visited = set()
    stack = deque([start])
    
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex, end=' ')  # Process the vertex as needed
            # It's important to add neighbors in reverse order to visit them in the correct order
            for neighbor in reversed(graph[vertex]):
                if neighbor not in visited:
                    stack.append(neighbor)

# Example usage
dfs_iterative(graph, 'A')

Applications of DFS

DFS is used in various applications, including:

• Detecting cycles in a graph which is crucial in many applications such as deadlock detection.
• Path finding between two nodes in a graph.
• Topological sorting of a graph.
• Finding connected components in a graph.
• Solving puzzles with only one solution, such as mazes.